﻿#define _CRT_SECURE_NO_WARNINGS

//#include<iostream>
//#include<set>
//using namespace std;
//
//int main()
//{
//    // 去重+升序排序
//    set<int> s;
//    // 去重+降序排序（给一个大于的仿函数）
//    // set<int, greater<int>> s;
//    s.insert(5);
//    s.insert(2);
//    s.insert(7);
//    s.insert(5);
//
//    //set<int>::iterator it = s.begin();
//    auto it = s.begin();
//    while (it != s.end())
//    {
//        // error C3892: “it”: 不能给常量赋值
//        // *it = 1;
//        cout << *it << " ";
//        ++it;
//    }
//    cout << endl;
//
//    // 插入一段initializer_list到表值，已经存在的值插入失败
//    s.insert({ 2, 8, 3, 9 });
//    for (auto e : s)
//    {
//        cout << e << " ";
//    }
//    cout << endl;
//
//    set<string> strset = { "sort", "insert", "add" };
//    // 遍历string比较ascII码大小顺序遍历的
//    for (auto e : strset)
//    {
//        cout << e << " ";
//    }
//    cout << endl;
//}

//#include<iostream>
//#include<set>
//using namespace std;
//
//int main()
//{
//	// 插入数据
//	set<int> s = { 4,2,7,2,8,5,9 };
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	// 删除最⼩值 
//	s.erase(s.begin());
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	// 直接删除x 
//	int x;
//	cin >> x;
//	int num = s.erase(x);
//	if (num == 0)
//	{
//		cout << x << "不存在！" << endl;
//	}
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	// 直接查找在利⽤迭代器删除x 
//	cin >> x;
//	auto pos = s.find(x);
//	if (pos != s.end())
//	{
//		s.erase(pos);
//	}
//	else
//
//	{
//		cout << x << "不存在！" << endl;
//	}
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;
//}

//#include<iostream>
//#include<set>
//using namespace std;
//
//int main()
//{
//	set<int> s = { 4,2,7,2,8,5,9 };
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	// 利⽤count间接实现快速查找 
//	int x;
//	cin >> x;
//	if (s.count(x))
//	{
//		cout << x << "在！" << endl;
//	}
//	else
//	{
//		cout << x << "不存在！" << endl;
//	}
//	return 0;
//}


//#include<iostream>
//
//#include<set>
//
//using namespace std;
//
//int main()
//{
//	std::set<int> myset;
//	for (int i = 1; i < 10; i++)
//		myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
//
//	for (auto e : myset)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	// 实现查找到的[itlow,itup)包含[30, 60]区间 
//
//	// 返回 >= 30 
//	auto itlow = myset.lower_bound(30);
//	// 返回 > 60 
//	auto itup = myset.upper_bound(60);
//
//	// 删除这段区间的值 
//	myset.erase(itlow, itup);
//	for (auto e : myset)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	return 0;
//}


//#include<iostream>
//#include<set>
//using namespace std;
//
//int main()
//{
//	// 相⽐set不同的是，multiset是排序，但是不去重 
//	multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };
//	auto it = s.begin();
//	while (it != s.end())
//	{
//		cout << *it << " ";
//		++it;
//	}
//	cout << endl;
//
//	//// 相⽐set不同的是，x可能会存在多个，find查找中序的第⼀个 
//	//int x;
//	//cin >> x;
//	//auto pos = s.find(x);
//	//while (pos != s.end() && *pos == x)
//	//{
//	//	cout << *pos << " ";
//	//	++pos;
//	//}
//	//cout << endl;
//
//	//// 相⽐set不同的是，count会返回x的实际个数 
//	//int x;
//	//cin >> x;
//	//cout << s.count(x) << endl;
//
//	// 相⽐set不同的是，erase给值时会删除所有的x 
//	int x;
//	cin >> x;
//	s.erase(x);
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;
//}



//#include<iostream>
//#include<map>
//#include<string>
//using namespace std;
//
//int main()
//{
//	// initializer_list构造及迭代遍历 
//	map<string, string> dict = { {"left", "左边"}, {"right", "右边"},
//   {"insert", "插入"},{ "string", "字符串" } };
//
//	//map<string, string>::iterator it = dict.begin();
//	auto it = dict.begin();
//	while (it != dict.end())
//	{
//		//cout << (*it).first <<":"<<(*it).second << endl;
//
//
//		// map的迭代基本都使⽤operator->,这⾥省略了⼀个-> 
//		// 第⼀个->是迭代器运算符重载，返回pair*，第⼆个箭头是结构指针解引⽤取pair数据
//		//cout << it.operator->()->first << ":" << it.operator->()-> second << endl;
//		cout << it->first << ":" << it->second << endl;
//		++it;
//	}
//	cout << endl;
//
//	return 0;
//}


//#include<iostream>
//#include<map>
//using namespace std;
//
//int main()
//{
//	// initializer_list构造及迭代遍历 
//	map<string, string> dict = { {"left", "左边"}, {"right", "右边"},{"insert", "插⼊"},{ "string", "字符串" } };
//
//	// insert插⼊pair对象的4种⽅式
//	// 1.先构造对象在插入
//	pair<string, string> kv1("first", "第⼀个");
//	dict.insert(kv1);
//
//	// 2.匿名对象插入
//	dict.insert(pair<string, string>("second", "第⼆个"));
//
//	// 3.make_pair函数模版插入
//	dict.insert(make_pair("sort", "排序"));
//
//	// 4.隐式类型转换+匿名对象插入（最好用）
//	dict.insert({ "auto", "⾃动的" });
//
//	return 0;
//}

//#include<iostream>
//#include<map>
//using namespace std;
//
//int main()
//{
//    // initializer_list构造及迭代遍历 
//    map<string, string> dict = { {"left", "左边"}, {"right", "右边"},{"insert", "插⼊"},{ "string", "字符串" } };
//
//    string str;
//    while (cin >> str)
//    {
//        auto ret = dict.find(str);
//        if (ret != dict.end())
//        {
//            cout << "->" << ret->second << endl;
//        }
//        else
//        {
//            cout << "无此单词，请重新输入" << endl;
//        }
//    }
//    return 0;
//}

//#include<iostream>
//#include<map>
//#include<string>
//using namespace std;
//
//int main()
//{
//	map<string, string> dict;
//	dict.insert(make_pair("sort", "排序"));
//
//	// key不存在->插⼊ {"insert", string()} 
//	dict["insert"];
//	// 插⼊+修改 
//	dict["left"] = "左边";
//	// 修改 
//	dict["left"] = "左边、剩余";
//	// key存在->查找 
//	cout << dict["left"] << endl;
//
//	return 0;
//}


//#include<iostream>
//#include<map>
//#include<string>
//using namespace std;
//
//int main()
//{
//	// 利⽤[]插⼊+修改功能，巧妙实现统计⽔果出现的次数 
//	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };
//	map<string, int> countMap;
//	for (const auto& str : arr)
//	{
//		// []先查找⽔果在不在map中 
//		// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 0}，同时返回次数的引⽤，++⼀下就变成1次了
//		// 2、在，则返回⽔果对应的次数++ 
//		countMap[str]++;
//	}
//	for (const auto& e : countMap)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//	cout << endl;
//	return 0;
//}


//class Solution {
//
//public:
//	Node* copyRandomList(Node* head) {
//		map<Node*, Node*> nodeMap;
//		Node* copyhead = nullptr, * copytail = nullptr;
//		Node* cur = head;
//		while (cur)
//		{
//			if (copytail == nullptr)
//			{
//				copyhead = copytail = new Node(cur->val);
//			}
//			else
//
//			{
//				copytail->next = new Node(cur->val);
//				copytail = copytail->next;
//			}
//
//			// 原节点和拷⻉节点map kv存储 
//			nodeMap[cur] = copytail;
//			cur = cur->next;
//		}
//		// 处理random 
//		cur = head;
//		Node* copy = copyhead;
//		while (cur)
//		{
//			if (cur->random == nullptr)
//			{
//				copy->random = nullptr;
//			}
//			else
//
//			{
//				copy->random = nodeMap[cur->random];
//			}
//			cur = cur->next;
//			copy = copy->next;
//		}
//		return copyhead;
//	}
//};


//class Solution {
//
//public:
//	vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//		set<int> s1(nums1.begin(), nums1.end());
//		set<int> s2(nums2.begin(), nums2.end());
//		// 因为set遍历是有序的，有序值，依次⽐较 
//		// 小的++，相等的就是交集 
//		vector<int> ret;
//		auto it1 = s1.begin();
//		auto it2 = s2.begin();
//		while (it1 != s1.end() && it2 != s2.end())
//		{
//			if (*it1 < *it2)
//			{
//				it1++;
//			}
//			else if (*it1 > *it2)
//			{
//				it2++;
//			}
//			else
//
//			{
//				ret.push_back(*it1);
//				it1++;
//				it2++;
//			}
//		}
//		return ret;
//	}
//};

//class Solution 
//{
//public:
//	ListNode* detectCycle(ListNode* head) 
//	{
//		set<ListNode*> s;
//		ListNode* cur = head;
//
//		while (cur)
//		{
//			auto ret = s.insert(cur);
//			if (ret.second == false)
//				return cur;
//
//			cur = cur->next;
//		}
//	return nullptr;
//	}
//};

//class Solution 
//{
//public:
//	struct Compare
//
//	{
//		bool operator()(const pair<string, int>& x, const pair<string, int>& y) const
//		{
//			return x.second > y.second;
//		}
//	};
//
//	vector<string> topKFrequent(vector<string>& words, int k) 
//	{
//		map<string, int> countMap;
//		for (auto& e : words)
//		{
//			countMap[e]++;
//		}
//
//		vector<pair<string, int>> v(countMap.begin(), countMap.end());
//		// 仿函数控制降序
//		stable_sort(v.begin(), v.end(), Compare());
//		//sort(v.begin(), v.end(), Compare());
//
//
//		// 取前k个 
//		vector<string> strV;
//		for (int i = 0; i < k; ++i)
//		{
//			strV.push_back(v[i].first);
//		}
//		return strV;
//	}
//};


